【图论笔记】权转移法（2）：初始电荷量和放电规则

1. 初始电荷量

设 $\mathcal{P}$ 是全体可平面图构成的图族．权转移法通常在这个图族的某个子族上实施．

注意：可平面图和平面图是不同的两个概念：存在平面嵌入的图是可平面图；固定可平面图的一个平面嵌入，从而得到的一个拓扑图是平面图。一言以蔽之，可平面图仍然是抽象的图，但平面图是平面的一个拓扑子空间。

设 $\mathcal{G}$ 是 $\mathcal{P}$ 的一个子族．再设 $G\in \mathcal{G}$ ．固定图 $G$ 在欧氏平面上的一个平面嵌入．下面的问题是如何在 $G$ 上设置初始电荷量 $ch_0(\cdot)$ ．

初始电荷量的常见设置方法有三种，即顶点充电法、面充电法和均衡充电法．

顶点充电法的初始电荷量的设置如下：
$ch_0(x)=\left\{ \begin{aligned} &2d(x)-6, & x&\in V(G)\\ &d(x)-6, & x&\in F(G). \end{aligned} \right.$

使用欧拉公式可以算出，在顶点充电法之下， $G$ 的初始电荷量的总和为
$\sum_{x\in V(G)\cup F(G)}ch_0(x)=4e(G)-6v(G)+2e(G)-6f(G)=-12<0.$

面充电法的初始电荷量的设置如下：
$ch_0(x)=\left\{ \begin{aligned} &d(x)-6, & x&\in V(G)\\ &2d(x)-6, & x&\in F(G). \end{aligned} \right.$

使用欧拉公式很容易算出，在面充电法之下， $G$ 的初始电荷量的总和为
$\sum_{x\in V(G)\cup F(G)}ch_0(x)=2e(G)-6v(G)+4e(G)-6f(G)=-12<0.$

均衡充电法的初始电荷量的设置如下：
$ch_0(x)=d(x)-4,~~~x\in V(G)\cup F(G).$

再次使用欧拉公式可得， $G$ 在均衡充电法下的初始电荷量的总和为
$\sum_{x\in V(G)\cup F(G)}ch_0(x)=2e(G)-4v(G)+2e(G)-4f(G)=-8<0.$

在三种常见的充电法里，初始电荷量的总和都是负．所以如果在某组放电规则下放电之后，出现每个顶点和每个面的电荷量都是非负，那么一定存在某个矛盾．

也就是说：图 $G$ 原本没有某个性质或结构，但是我们假定它有，结果导致了矛盾．实际上，【权转移法(0)】中的例题就是这样证明的．

那么如何设计放电规则呢？

这就是一件很艺术的事情了．一般原则上是就近放电，但并不绝对．

事实上，正是由于放电规则设计的不同（以及初始电荷量的不同），导致了我们能够借助权转移法，找到不同的不可回避集．

而恰恰是这些不同的不可回避集，能在不同的图论问题中起到关键的作用．

下一节我们将给出第二个简单例子，来看一下：变更初始电荷量和放电规则可以给我们带来什么．